Prawie szablon [A]

Limit pamięci: 192 MB

Szablonem słowa nazwiemy takie słowo , że wszystkie wystąpienia w pokrywają całkowicie słowo (tzn. każda litera słowa znajduje się wewnątrz jakiegoś spójnego fragmentu równego ). Prawie szablonem słowa nazwiemy takie słowo , że jest podsłowem (tj. spójnym fragmentem) oraz jest szablonem pewnego nadsłowa słowa . Poniższy rysunek pokazuje, dlaczego słowo aabaa jest prawie szablonem słowa aaaabaabaaaba:

Dla danego słowa należy wyznaczyć liczbę jego prawie szablonów oraz najkrótszy z nich.

Wejście

W jedynym wierszu standardowego wejścia znajduje się niepuste słowo o długości nie większej niż . Składa się ono z małych liter alfabetu angielskiego.

Wyjście

W pierwszym wierszu standardowego wyjścia należy wypisać liczbę prawie szablonów słowa . W drugim wierszu należy wypisać najkrótszy prawie szablon słowa . Jeśli jest więcej niż jeden najkrótszy prawie szablon, to należy wypisać leksykograficznie najmniejszy spośród najkrótszych prawie szablonów.

Przykład

Dla danych wejściowych:

aaaabaabaaaba

poprawną odpowiedzią jest:

10
aabaa

Podane w przykładowym wejściu słowo ma dziesięć prawie szablonów: aaaabaabaaab, aaaabaabaaaba, aaabaaba, aaabaabaa, aaabaabaaa, aaabaabaaaba, aabaa, aabaabaa, aabaabaaa oraz abaabaaa.

Autor zadania: Tomasz Idziaszek.